|
In computer science, tabulation hashing is a method for constructing universal families of hash functions by combining table lookup with exclusive or operations. It is simple and fast enough to be usable in practice, and has theoretical properties that (in contrast to some other universal hashing methods) make it usable with linear probing, cuckoo hashing, and the MinHash technique for estimating the size of set intersections. The first instance of tabulation hashing is Zobrist hashing (1969). It was later rediscovered by and studied in more detail by . ==Method== Let ''p'' denote the number of bits in a key to be hashed, and ''q'' denote the number of bits desired in an output hash function. Let ''r'' be a number smaller than ''p'', and let ''t'' be the smallest integer that is at least as large as ''p''/''r''. For instance, if ''r'' = 8, then an ''r''-bit number is a byte, and ''t'' is the number of bytes per key. The key idea of tabulation hashing is to view a key as a vector of ''t'' ''r''-bit numbers, use a lookup table filled with random values to compute a hash value for each of the ''r''-bit numbers representing a given key, and combine these values with the bitwise binary exclusive or operation. The choice of ''r'' should be made in such a way that this table is not too large; e.g., so that it fits into the computer's cache memory. The initialization phase of the algorithm creates a two-dimensional array ''T'' of dimensions 2''r'' by ''t'', and fills the array with random numbers. Once the array ''T'' is initialized, it can be used to compute the hash value ''h''(''x'') of any given key ''x''. To do so, partition ''x'' into ''r''-bit values, where ''x''0 consists of the low order ''r'' bits of ''x'', ''x''1 consists of the next ''r'' bits, etc. (E.g., again, with ''r'' = 8, ''x''''i'' is just the ''i''th byte of ''x''). Then, use these values as indices into ''T'' and combine them with the exclusive or operation: :''h''(''x'') = ''T''()() ⊕ ''T''()() ⊕ ''T''()() ⊕ ... 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「tabulation hashing」の詳細全文を読む スポンサード リンク
|